class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        m = len(image)
        n = len(image[0])
        c = image[sr][sc]
        if c == newColor:
            return image
        now = {(sr, sc)}
        while now:
            next_st = set()
            for x, y in now:
                image[x][y] = newColor
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n and image[ux][uy] == c:
                        next_st.add((ux, uy))
            now = next_st
        return image
